﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
//请你将两个数相加，并以相同形式返回一个表示和的链表。
//你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
//示例 1：
//输入：l1 = [2, 4, 3], l2 = [5, 6, 4]
//输出：[7, 0, 8]
//解释：342 + 465 = 807.
//示例 2：
//输入：l1 = [0], l2 = [0]
//输出：[0]
//示例 3：
//输入：l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
//输出：[8, 9, 9, 9, 0, 0, 0, 1]

//struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
//    struct ListNode* newhead = NULL;
//    struct ListNode* tail = NULL;
//    int carry = 0;
//    while (l1 || l2)
//    {
//        int n1 = l1 ? l1->val : 0;
//        int n2 = l2 ? l2->val : 0;
//        int sum = n1 + n2 + carry;
//        if (newhead == NULL)
//        {
//            newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//            newhead->val = sum % 10;
//            newhead->next = NULL;
//        }
//        else
//        {
//            struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
//            newnode->val = sum % 10;
//            newnode->next = NULL;
//            tail->next = newnode;
//            tail = newnode;
//        }
//
//        if (l1)
//            l1 = l1->next;
//        if (l2)
//            l2 = l2->next;
//        carry = sum / 10;
//
//    }
//    if (carry > 0)
//    {
//        struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
//        newnode->val = carry;
//        newnode->next = NULL;
//        tail->next = newnode;
//    }
//    return newhead;
//
//}


//拷贝复杂链表
struct Node* copyRandomList(struct Node* head)
{
    //把新链表连接起来
    struct Node* cur = head;
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = next;
    }
    cur = head;
    //创建新链表的头和尾
    struct Node* newhead = NULL;
    struct Node* tail = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (newhead == NULL)
        {
            newhead = tail = copy;
        }
        else
        {
            tail->next = copy;
            tail = tail->next;
        }
        //还原原来链表的指向
        cur->next = next;

        cur = next;
    }
    return newhead;
}